package sort;

import java.util.ArrayList;
import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int[] arr = {8, 3, 6, 1, 8, 9, 3, 2};
        System.out.println("冒泡排序===" + Arrays.toString(bubbleSort(arr )));


        System.out.println("快速排序===" + Arrays.toString(quickSort(arr, 0, arr.length - 1)));


        ArrayList<Object> objects = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            objects.add(i);
        }
        System.out.println(objects);

    }


    /**
     * 1,冒泡排序
     * -----------------------------------------------
     * 1,最外层循环表示要循环n-1次
     * 2，第二层每次都从头开始
     * 3，如果当前元素大于下一个元素，就交换顺序
     * --------------------------------------------------
     *
     * @param arr
     */
    public static int[] bubbleSort(int[] arr) {
        for (int i = 1; i < arr.length ; i++) {//外层控制，遍历次数
            for (int j = 0; j < arr.length - i; j++) {//控制遍历的右边界
                if (arr[j] > arr[j + 1]) {//这个控制是否保持相同元素排序   比如 8（1），8（2）
                    swap(arr, j, j + 1);//交换
                }
            }
        }
        return arr;
    }

    /**
     * 2,选择排序
     * --------------------------------------
     * 原理：每次都从待排序的数据中选择最小的，排序到有序的元素中
     * 实现：
     * 1，循环n-1次
     * 2，在剩余的元素里面查找最小的
     * 3，最小的和未排序的那个交换位置，实现排序
     */
    public static int[] selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            for (int j = i; j < arr.length; j++) {//找到最小元素的下标
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            if (index != i) {
                swap(arr, index, i);
            }
        }
        return arr;
    }

    /**
     * 3,插入排序
     * ----------------------------
     * 把待排序的元素插入到已经排序好的序列中去
     * 实现：从数组1开始到最后结束
     * 和已经排序好的比较，遇到比自己大的，剩余的元素朝后移动。然后把该元素安插到这个位置上去
     */
    public static int[] insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int item = arr[i];
            for (int j = 0; j < i; j++) {//遍历查找要插入的位置
                if (item < arr[j]) {
                    //坐标j到坐标i-1的向后移
                    for (int k = i - 1; k >= j; k--) {
                        arr[k + 1] = arr[k];
                    }
                    arr[j] = item;
                    break;
                }
            }
        }
        return arr;
    }

    /**
     * 4,希尔排序
     */
    public static int[] hillSort(int[] arr) {


        return arr;

    }

    /**
     * 5,快速排序
     * -------------------------------
     * 实现：
     * 1，选取分界值 item
     * 2，if right指针<item arr[r]移到a[l]同时left++,结束本次循环;否则r--;
     * 3,if le>item a[l]移到啊a[r]同时r++,结束本次循环；否则l++;
     * 4,l=r结束循环，给分界值安排位置
     * 5，递归左边
     * 5,递归右边
     * ------------------------------------
     * 递归的三大要素
     * 明确函数功能；寻找结束条件；寻找子问题
     *
     * @return
     */
    public static int[] quickSort(int[] arr, int left, int right) {
        if (left >= right) {//结束条件
            return arr;
        }
        int item = arr[left];//选取最左边的第一个为分界值
        int rightIndex = right, leftIndex = left;
        while (leftIndex < rightIndex) {//大的结束条件
            while (leftIndex < rightIndex && arr[rightIndex] > item) {//左边或者右边的小循环结束条件
                rightIndex--;
            }
            if (leftIndex < rightIndex) {
                arr[leftIndex++] = arr[rightIndex];
            }

            while (leftIndex < rightIndex && arr[leftIndex] < item) {
                leftIndex++;
            }
            if (leftIndex < rightIndex) {
                arr[rightIndex--] = arr[leftIndex];
            }

        }

        arr[leftIndex] = item;//安插分界值
        quickSort(arr, 0, leftIndex - 1);
        quickSort(arr, leftIndex + 1, right);
        return arr;
    }


    public static int[] quickSort2(int[] arr, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return arr;
        }
        i = low;
        j = high;
        //temp就是基准位
        temp = arr[low];

        while (i < j) {
            //先看右边，依次往左递减
            while (temp <= arr[j] && i < j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp >= arr[i] && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort2(arr, low, j - 1);
        //递归调用右半数组
        quickSort2(arr, j + 1, high);
        return arr;
    }


    /**
     * 6,归并排序
     */
    public static void mergeSort(int[] arr) {

    }

    /**
     * 7，堆排序
     */
    public static void heapSort(int[] arr) {

    }

    /**
     * 8，计数排序
     * --------------------------------------------
     * 原理：找出原数组中元素值最大的，记为max;
     * 创建一个新数组count，其长度是max加1，其元素默认值都为0。
     * 遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
     * 创建结果数组result，起始索引index
     * 遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素
     * 返回结果数组result
     */
    public static int[] countSort(int[] A) {
        // 找出数组A中的最大值
        int max = Integer.MIN_VALUE;
        for (int num : A) {
            max = Math.max(max, num);
        }
        // 初始化计数数组count
        int[] count = new int[max + 1];
        // 对计数数组各元素赋值
        for (int num : A) {
            count[num]++;
        }
        // 创建结果数组
        int[] result = new int[A.length];
        // 创建结果数组的起始索引
        int index = 0;
        // 遍历计数数组，将计数数组的索引填充到结果数组中
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                result[index++] = i;
                count[i]--;
            }
        }
        // 返回结果数组
        return result;
    }

    /**
     * 9，桶排序
     */
    public static void bucketSort(int[] arr) {

    }
    /**
     *10，基数排序
     */


    /**
     * 交换数组的两个元素
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }




}





